On traffic domination in communication networks

摘要

Input data for communication network design/optimizationproblems involving multi-hour or uncertain tra c can consist of a largeset of tra c matrices. These matrices are explicitly considered in prob-lem formulations for link dimensioning. However, many of these matricesare usually dominated by others so only a relatively small subset of ma-trices would be su cient to obtain proper link capacity reservations, sup-porting all original tra c matrices. Thus, elimination of the dominatedmatrices leads to substantially smaller optimization problems, makingthem treatable by contemporary solvers. In the paper we discuss theissues behind detecting domination of one tra c matrix over another.We consider two basic cases of domination: (i) total domination whenthe same tra c routing must be used for both matrices, and (ii) ordi-nary domination when tra c dependent routing can be used. The paperis based on our original results and generalizes the domination resultsknown for fully connected networks.